package middle;

public class Solution_97 {

    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length()) {
            return false;
        }
        boolean[][] flags = new boolean[s1.length() + 1][s2.length() + 1];
        flags[0][0] = true;
        for (int i = 1; i <= s3.length(); i++) {
            // j = s2选了几个字母
            for (int j = 0; j <= i; j++) {
                if (i - j - 1 < s1.length() && j - 1 < s2.length()) {
                    boolean flag = (j < i &&  s1.charAt(i - j - 1) == s3.charAt(i - 1) && flags[i - j - 1][j])
                    || (j > 0 && s2.charAt(j - 1) == s3.charAt(i - 1) && flags[i - j][j - 1]);
                    flags[i - j][j] = flag;
                }
            }
        }
        return flags[s1.length()][s2.length()];
    }
    /*public boolean isInterleave(String s1, String s2, String s3) {
        if (s3.length() == 0) {
            return s1.length() == 0 && s2.length() == 0;
        } else if (s1.length() == 0) {
            return s2.equals(s3);
        } else if (s2.length() == 0) {
            return s1.equals(s3);
        }
        boolean flag = false;
        if (s1.charAt(s1.length() - 1) == s3.charAt(s3.length() - 1)) {
            flag = isInterleave(s1.substring(0, s1.length() - 1), s2, s3.substring(0, s3.length() - 1));
        }
        if (!flag && s2.charAt(s2.length() - 1) == s3.charAt(s3.length() - 1)) {
            flag = isInterleave(s1, s2.substring(0, s2.length() - 1), s3.substring(0, s3.length() - 1));
        }
        return flag;
    }*/

    public static void main(String[] args) {
        Solution_97 model = new Solution_97();
        System.out.println(model.isInterleave("aabcc", "dbbca", "aadbbcbcac"));
                System.out.println(model.isInterleave("aabcc", "dbbca", "aadbbbaccc"));
                System.out.println(model.isInterleave("", "", ""));
                System.out.println(model.isInterleave("a", "", "a"));
                System.out.println(model.isInterleave("a", "", "c"));
                System.out.println(model.isInterleave("", "b", "b"));
                System.out.println(model.isInterleave("a", "b", "a"));
    }
}
